package com.anjingsi.tools.recall;

import com.anjingsi.tools.utils.PrintArray;

import java.util.Random;

/**
 * @program: 迷宫回溯
 * @description 数组中值表示的意思 0 初始化  1 墙 2 走过的路  6起点  8 终点
 * @author: 安静思
 * @create: 2019-12-19 13:57
 **/
public class MazeRecall {

    private int[][] array;
    /**
     * 初始化数组
     * @param row 行
     * @param column 行
     * @param num 随机障碍的个数
     * @return
     */
    private int[][] initMaze(int row,int column,int num){
        array = new int[row][column];
        //设置四周为墙
        for(int i = 0 ; i < row ; i++){
            array[0][i] = 1 ;
            array[column-1][i] = 1;
        }
        for(int i = 0 ; i < column ; i++){
            array[i][0] = 1 ;
            array[i][row-1] = 1;
        }
        //生成随机障碍
        Random random = new Random();
        for(int i = 0 ; i < num ; i++){
            array[random.nextInt(row-4)+2][random.nextInt(column-4)+2] = 1 ;
        }
        //随机的起点
        array[random.nextInt(row-2)+1][random.nextInt(column-2)+1] = 6 ;
        //随机的终点
        array[random.nextInt(row-2)+1][random.nextInt(column-2)+1] = 8 ;
        return array;
    }

    /**
     * 获取起点坐标
     * @return
     */
    private Coordinate getStartCoordinate(){
        for (int i = 1; i < array.length-1; i++) {
            for (int j = 1; j < array[0].length-1; j++) {
                if(array[i][j] == 6){
                    return new Coordinate(i,j);
                }
            }
        }
        throw new RuntimeException("没有找到起点");
    }

    /**
     * 获取终点坐标
     * @return
     */
    private Coordinate getEndCoordinate(){
        for (int i = 1; i < array.length-1; i++) {
            for (int j = 1; j < array[0].length-1; j++) {
                if(array[i][j] == 8){
                    return new Coordinate(i,j);
                }
            }
        }
        throw new RuntimeException("没有找到终点");
    }

    /**
     * 开始找路
     * @param startCoordinate 开始的坐标
     * @param endCoordinate  终点的坐标
     * @return
     */
    private boolean setWay(Coordinate startCoordinate,Coordinate endCoordinate){
        //起点与终点相同则认为已经找到出路
        if(startCoordinate.getRow() == endCoordinate.getRow() && startCoordinate.getColumn() == endCoordinate.getColumn()){
            return true;
        }
        int temp = array[startCoordinate.getRow()][startCoordinate.getColumn()];
        if(temp == 1 || temp == 3 || temp == 2){
            return false;
        }
        if(temp == 0){
            array[startCoordinate.getRow()][startCoordinate.getColumn()] = 2;
        }
        //计算最优的路径  主要计算先是左右还是上下
        if(startCoordinate.getColumn() - endCoordinate.getColumn() < 0){
            //终点在起点右边
            if(right(startCoordinate,endCoordinate)){
                return true;
            }
        }else if(startCoordinate.getColumn() - endCoordinate.getColumn() > 0){
            //终点在起点左边
            if(left(startCoordinate,endCoordinate)){
                return true;
            }
        }
        if(startCoordinate.getRow() - endCoordinate.getRow() > 0){
            //终点在起点的上边
            if(up(startCoordinate,endCoordinate)){
                return true;
            }
        }else if(startCoordinate.getRow() - endCoordinate.getRow() < 0){
            //终点在起点的下边
            if(down(startCoordinate,endCoordinate)){
                return true;
            }
        }
        /*下->左->右->上*/
        if(down(startCoordinate,endCoordinate)){
            return true;
        }else if(left(startCoordinate,endCoordinate)){
            return true;
        }else if(right(startCoordinate,endCoordinate)){
            return true;
        }else if(up(startCoordinate,endCoordinate)){
            return true;
        }
        return false;
    }

    private boolean up(Coordinate startCoordinate,Coordinate endCoordinate){
        return setWay(new Coordinate(startCoordinate.getRow()-1,startCoordinate.getColumn()),endCoordinate);
    }

    private boolean down(Coordinate startCoordinate,Coordinate endCoordinate){
        return setWay(new Coordinate(startCoordinate.getRow()+1,startCoordinate.getColumn()),endCoordinate);
    }

    private boolean right(Coordinate startCoordinate,Coordinate endCoordinate){
        return setWay(new Coordinate(startCoordinate.getRow(),startCoordinate.getColumn()+1),endCoordinate);
    }

    private boolean left(Coordinate startCoordinate,Coordinate endCoordinate){
        return setWay(new Coordinate(startCoordinate.getRow(),startCoordinate.getColumn()-1),endCoordinate);
    }

    public static void main(String[] args) {
        MazeRecall mazeRecall = new MazeRecall();
        mazeRecall.initMaze(11, 11,16);
        PrintArray.printArray(mazeRecall.array);
        Coordinate startCoordinate = mazeRecall.getStartCoordinate();
        Coordinate endCoordinate = mazeRecall.getEndCoordinate();
        mazeRecall.setWay(startCoordinate,endCoordinate);
        System.out.println();
        PrintArray.printArray(mazeRecall.array);
    }

}
